|
In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete, which means that they are suitable as a general model of computation and can represent any mathematical expression from its simple notation. Markov algorithms are named after the Soviet mathematician Andrey Markov, Jr. Refal is a programming language based on Markov algorithms. ==Algorithm== The ''Rules'' is a sequence of pair of strings, usually presented in the form of ''pattern'' → ''replacement''. Each rule may be either ordinary or terminating. Given an ''input'' string: #Check the Rules in order from top to bottom to see whether any of the ''patterns'' can be found in the ''input'' string. #If none is found, the algorithm stops. #If one (or more) is found, use the first of them to replace the leftmost occurrence of matched text in the ''input'' string with its ''replacement''. #If the rule just applied was a terminating one, the algorithm stops. #Go to step 1. Note that after each rule application the search starts over from the first rule. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Markov algorithm」の詳細全文を読む スポンサード リンク
|